//「一本通 3.1 练习 1」新的开始,此题不能采用prim算法，因为实际上会分成多颗独立的子树
//故采用kruska算法，在加入每条边时，判断是加边（建立电网）还是不加边（建立发电站）
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=300;
int v[MAXN+1];
int p[MAXN+1][MAXN+1];
struct Edge
{
    int from,to,weight;
    bool operator<(const Edge other)const {
        return weight<other.weight;
    }
};
Edge edges[MAXN*MAXN];

int n;
int minv[MAXN+1];//minv[i]表示以i为根的生成子树建立电站的最小费用
int sump[MAXN+1];//sump[i]表示以i为根的生成子树边=连成电网的费用和
struct UFS {
    int fa[MAXN+1];
    void init(){
        for(int i=1;i<=n;i++) fa[i]=i;
    }
    int find_set(int x){
        if (fa[x]!=x) fa[x]=find_set(fa[x]);//路径压缩，此处用if不能用while
        return fa[x];
    }
    void union_set(int x,int y){
        int hx=find_set(x);
        int hy=find_set(y);
        fa[hy]=hx;
    }
};
UFS ufs;
int ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>p[i][j];
    int edgenum=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            edges[edgenum++]={i,j,p[i][j]};
        }
    
    for(int i=1;i<=n;i++) minv[i]=v[i];
    sort(edges,edges+edgenum);
    ufs.init();
    for(int i=0;i<edgenum;i++){
        int u=edges[i].from;
        int v=edges[i].to;
        int w=edges[i].weight;
        int ru=ufs.find_set(u);
        int rv=ufs.find_set(v);
        if (ru!=rv&&(w<minv[ru]||w<minv[rv])){//当以此边建立电网的费用比两颗子树任一颗建立电站的费用小时，使用此边建立电网
            if (minv[ru]<=minv[rv]){ //哪一颗子树建立电站的费用小则保留，另一颗子树则加入此颗中
                ufs.union_set(ru,rv);
                sump[ru]+=w+sump[rv];
                minv[rv]=0;
            }else {
                ufs.union_set(rv,ru);
                sump[rv]+=w+sump[ru];
                minv[ru]=0;
            }
        }
    }
        
    for(int i=1;i<=n;i++)
        if (ufs.fa[i]==i) ans+=minv[i]+sump[i];
    cout<<ans;
}

